using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Windows.Forms;

namespace Tetris
{
    #region structures

    enum Direction { N=0, E=1, S=2, W=3 };

    struct Waypoint
    {
        public Direction direction;
        public Point position;

        public Waypoint(Point p, Direction dir)
        {
            direction = dir;
            position = p;
        }
    }

    struct Possibility
    {
        public bool north;
        public bool east;
        public bool south;
        public bool west;

        public Possibility(Possibility posibility)
        {
            north = posibility.north;
            south = posibility.south;
            west = posibility.west;
            east = posibility.east;
        }

        public bool IsDirection(Direction direction)
        {
            switch (direction)
            {
                case Direction.N:
                    return north;                
                case Direction.S:
                    return south;
                case Direction.E:
                    return east;
                case Direction.W:
                    return west;                   
            }
            return false;
        }

        public bool IsDirection(int i)
        {
            return IsDirection((Direction)i);
        }

        public void SetDirection(Direction direction)
        {
            switch (direction)
            {
                case Direction.N:
                    north = true;
                    return;
                case Direction.S:
                    south = true;
                    return;
                case Direction.E:
                    east = true;
                    return;
                case Direction.W:
                    west = true;
                    return;
            }
        }

        public void SetDirection(int i)
        {
            SetDirection((Direction)i);
        }

        public bool IsAnyDirection()
        {
            return north || west || south || east;
        }
    }
    #endregion

    class Engine
    {
        #region private_members

        static bool showPath = true,
                    advancedCalculations,
                    advancedOptimisation;
        static int range,
                   margin,
                   optimisationLowerBoundary, optimisationUpperBoundary;
        static double heuristicA,
                      heuristicX,
                      heuristicZ;
        static Block simulationBlock;
        static Brush brBrick,
                     brMovingBrick;
        static Pen boardContourPen;
        static double bestHeuristic;
        static Waypoint bestPosition;

        #endregion
        #region public_members
        
        public static Board mainBoard;
        public static Block currentBlock;
        public static Block nextBlock;
        public static Point currentBlockLocation;
        public static Point startingPoint;
        public static Possibility[,] possibilities;
        public static List<Waypoint> path = new List<Waypoint>();

        public static event EventHandler NewPath, NewNextBlock, AdvancedCalculationsChanged;
        
        #endregion
        #region accessors

        public static bool ShowPath
        {
            get { return showPath; }
            set { showPath = value; }
        }
        public static bool AdvancedCalculations
        {
            get { return advancedCalculations; }
            set
            {
                if (advancedCalculations != value)
                {
                    advancedCalculations = value;
                    if (AdvancedCalculationsChanged != null)
                    {
                        AdvancedCalculationsChanged(null, null);
                    }
                }
            }
        }
        public static bool AdvancedOptimisation
        {
            get { return advancedOptimisation; }
            set { advancedOptimisation = value; }
        }
        public static int OptimisationUpperBoundary
        {
            get { return optimisationUpperBoundary; }
            set { optimisationUpperBoundary = value; }
        }
        public static int OptimisationLowerBoundary
        {
            get { return optimisationLowerBoundary; }
            set { optimisationLowerBoundary = value; }
        }
        public static int Range
        {
            get { return range; }
            set
            {
                if (value > 0)
                    range = value;
            }
        }
        public static int Margin
        {
            get { return margin; }
        }
        private static Block NextBlock
        {
            get { return nextBlock; }
            set
            {
                nextBlock = value;
                if (NewNextBlock != null)
                    NewNextBlock(null, null);
            }
        }
        static public double HeuristicA
        {
            get { return heuristicA; }
            set { heuristicA = value; }
        }
        static public double HeuristicX
        {
            get { return heuristicX; }
            set { heuristicX = value; }
        }
        static public double HeuristicZ
        {
            get { return heuristicZ; }
            set { heuristicZ = value; }
        }

        #endregion

        public static void Init(Size s, int blockRange, double heurA, double heurX, double heurZ, bool advCalc, bool advOpt,
                                int optLowerBoundary, int optUpperBoundary)
        {
            brBrick = new SolidBrush(Color.Green);
            brMovingBrick = new SolidBrush(Color.Azure);
            boardContourPen = new Pen(Color.LightGray);

            margin = 2;
            mainBoard = new Board(s);

            range = blockRange;
            heuristicA = heurA;
            heuristicX = heurX;
            heuristicZ = heurZ;
            advancedCalculations = advCalc;
            advancedOptimisation = advOpt;

            optimisationLowerBoundary = optLowerBoundary;
            optimisationUpperBoundary = optUpperBoundary;

            Engine.currentBlock = null;
            NextBlock = Block.CreateRandom;

            startingPoint = new Point(s.Width / 2 - 1 + margin, s.Height - 3 + margin);

            path.Clear();
            ClearPossibilities(ref Engine.possibilities);
        }

        static void ClearPossibilities(ref Possibility [,]possib)
        {
            Engine.possibilities = new Possibility[mainBoard.Size.Width, mainBoard.Size.Height];
        }

        public static int Step()
        {
            int linesDisintegrated = 0;

            if (currentBlock == null)
            {
                bestPosition = new Waypoint(new Point(-10, -10), Direction.N);
                
                Engine.currentBlock = nextBlock;
                NextBlock = Block.CreateRandom;
                
                currentBlockLocation = startingPoint;
                if (advancedCalculations)
                {
                    if (!SearchPath(100000, Engine.mainBoard, currentBlock.Clone(), nextBlock.Clone())) return -1;
                }
                else
                {
                    if (!SearchPath(100000, Engine.mainBoard, currentBlock.Clone(), null)) return -1;
                }
                simulationBlock = (Block)currentBlock.Clone();
                return 0;
            }
            if (path.Count <= 0) //Block finished moving
            {
                //Adding block to the board
                mainBoard.AddBlock(currentBlock, currentBlockLocation);
                linesDisintegrated = mainBoard.RemoveLines();

                bestPosition = new Waypoint(new Point(-10, -10), Direction.N);
                
                Engine.currentBlock = nextBlock;
                NextBlock = Block.CreateRandom;
                currentBlockLocation = startingPoint;
                if (advancedCalculations)
                {
                    if (!SearchPath(100000, Engine.mainBoard, currentBlock.Clone(), nextBlock.Clone())) return -1;
                }
                else
                {
                    if (!SearchPath(100000, Engine.mainBoard, currentBlock.Clone(), null)) return -1;
                }
                
                if (bestHeuristic == double.MaxValue) return -1;
                simulationBlock = (Block)currentBlock.Clone();
                
                if (NewPath != null) NewPath(null, null);

                if (advancedOptimisation)
                    Optimize();
            }

            //Location on the possibilities table
            Waypoint waypoint = path[path.Count - 1];
            path.RemoveAt(path.Count - 1);
            
            currentBlock = (Block)simulationBlock.Clone();
            currentBlock.Rotate(waypoint.direction);
            currentBlockLocation = waypoint.position;

            return linesDisintegrated;
        }

        private static void Optimize()
        {
            int m = mainBoard.GetMaxHeight();
            if (m < optimisationLowerBoundary)
                Engine.AdvancedCalculations = false;
            else if (m > optimisationUpperBoundary)
                Engine.AdvancedCalculations = true;
        }

        private static void CheckRotations(Board board, Point p, Block block, Possibility[,] possibilities, Direction dir)
        {
            Block tmpBlock = block.Clone();
            tmpBlock.Rotate(dir);
            //This is the place to put restrictions on rotation
            int rot = (int)dir;
            for (int i = 1; i < 4; i++)
            {
                tmpBlock.RotateRight(); //Block rotation is (dir+1)%4
                rot++;
                rot &= 3;
                if (!possibilities[p.X, p.Y].IsDirection(rot))
                {
                    if (!IsBlockColliding(board, tmpBlock, p))
                        //possibilities[p.X, p.Y].SetDirection(i);
                        possibilities[p.X, p.Y].SetDirection(rot);
                    //else
                      //  break;
                }
                //else
                  //  break;                
            }
        }
        
        private static int FindPossibleMoves(Board board, Block block, int x, int y, Direction dir, Block futureBlock)
        {
            if (!possibilities[x, y].IsDirection(dir))
                return -1;

            Point currentPos = new Point(x, y);
            Block tmpBlock = (Block)block.Clone();
            tmpBlock.Rotate(dir);

            Point nextP = new Point(x, y - 1);
            if (IsBlockColliding(board, tmpBlock, nextP))
            {
                double heuristic;
                if (futureBlock != null)
                {
                    Point location = currentBlockLocation;
                    double h = bestHeuristic;
                    //Possibility[,] pos = CopyPossibilities(possibilities);
                    Possibility[,] pos = (Possibility [,])possibilities.Clone();
                    //if (SearchPath(1000000, (new Board(board)).AddBlock(block, currentPos), futureBlock.Clone(), null) == false) ;
                    SearchPath(1000000, (new Board(board)).AddBlock(tmpBlock, currentPos), futureBlock, null);

                    heuristic = bestHeuristic;
                    bestHeuristic = h;
                    possibilities = pos;
                    currentBlockLocation = location;
                }
                else
                    heuristic = CountHeuristics(new Board(board), tmpBlock, currentPos);

                if (heuristic < bestHeuristic)
                {
                    bestHeuristic = heuristic;
                    if ((futureBlock != null) || (!advancedCalculations))
                        bestPosition = new Waypoint(currentPos, dir);
                }

                return 0;
            }
            if (y == 0)
                return 0;
            
            possibilities[x, y - 1].SetDirection(dir);

            CheckRotations(board, nextP, block, Engine.possibilities, dir);

            for (int step = 1; step <= range; step++)
            {
                tmpBlock = (Block)block.Clone();
                for (int tmp = 0; tmp < 4; tmp++)
                {
                    if (x - step >= 0)
                        if (!possibilities[x - step, y - 1].IsDirection((Direction)tmp))
                            if (possibilities[x - step + 1, y - 1].IsDirection((Direction)tmp))
                            {
                                if (!IsBlockColliding(board, tmpBlock, new Point(x - step, y - 1)))
                                    possibilities[x - step, y - 1].SetDirection((Direction)tmp);
                            }

                    if (x + step < board.Size.Width - Engine.margin)
                        if (!possibilities[x + step, y - 1].IsDirection((Direction)tmp))
                            if (possibilities[x + step - 1, y - 1].IsDirection((Direction)tmp))
                                if (!IsBlockColliding(board, tmpBlock, new Point(x + step, y - 1)))
                                    possibilities[x + step, y - 1].SetDirection((Direction)tmp);

                    tmpBlock.RotateRight();
                }
            }
            return 0;
        }
        public static bool SearchPath(int end, Board board, Block block, Block futureBlock)
        {            
            int x, y;
            bestHeuristic = double.MaxValue;                            
            ClearPossibilities(ref Engine.possibilities);
            path.Clear();

            possibilities[startingPoint.X, startingPoint.Y].north = true;
            
            if(IsBlockColliding(board, block, startingPoint ))
                return false;

            for (y = board.Size.Height - 1; y >= 1; y--)
            {
                /* Block cannot be positioned completely beyond visible board borders
                 * so limit x to width - margin
                 */
                for (x = 0; x < board.Size.Width - Engine.Margin; x++)
                {
                    for (int i = 0; i < 4; i++)
                        FindPossibleMoves(board, block, x, y, (Direction)i, futureBlock);
                }
            }
            if((futureBlock != null)||(!advancedCalculations))
                FindPath();
            return true;
        }

        static void FindPath()
        {            
            path.Clear();
            path.Add(bestPosition);            
            if (!showPath)
            {
                path.Add(new Waypoint(startingPoint, Direction.N));                
                return;
            }
            int y = bestPosition.position.Y;
            int x = bestPosition.position.X;
            if (x < 0)
                return;
            int min, max, j;
            Direction currentDirection = bestPosition.direction;
            bool flag = false;

            for (; y < mainBoard.Size.Height; y++)
            {
                flag = false;
                j = 0;
                for (int i=(int)currentDirection; ; i = (i + 3) & 3)
                {
                    if (possibilities[x, y].IsDirection((Direction)i))
                    {
                        if (possibilities[x, y + 1].IsDirection((Direction)i))
                        {
                            currentDirection = (Direction)i;
                            path.Add(new Waypoint(new Point(x, y + 1), currentDirection));
                            flag = true;                            
                            break;
                        }
                    }
                    else
                        break;
                    j++;
                    if (j >= 4)
                        break;
                }

                if (flag) continue;

                min = x - range;
                if (min < 0) min = 0;
                max = x + range;
                /*
                if (max >= mainBoard.Size.Width)
                    max = mainBoard.Size.Width - 1;
                 */
                // We can limit searching for path to
                // 'width - margin' because there're no blocks
                // further to the right
                if (max >= mainBoard.Size.Width - Engine.Margin)
                    max = mainBoard.Size.Width - 1 - Engine.Margin;


                for (int i = 1; i <= range; i++)
                {
                    //left
                    if (x - i >= min)
                    {
                        if (possibilities[x - i, y].IsDirection((Direction)currentDirection))
                        {
                            if (possibilities[x - i + 1, y].IsDirection((Direction)currentDirection))
                            {
                                j = 0;
                                for (int ii = (int)currentDirection; ; ii = (ii + 3) & 3)
                                {
                                    if (possibilities[x - i, y].IsDirection((Direction)ii))
                                    {
                                        if (possibilities[x - i, y + 1].IsDirection((Direction)ii))
                                        {
                                            currentDirection = (Direction)ii;
                                            x -= i;
                                            path.Add(new Waypoint(new Point(x, y + 1), currentDirection));
                                            flag = true;                                            
                                            break;
                                        }
                                    }
                                    else
                                        break;
                                    j++;
                                    if (j >= 4)
                                        break;
                                }
                            }
                        }
                    }

                    //right
                    if (x + i <= max)
                    {
                        if (possibilities[x + i, y].IsDirection((Direction)currentDirection))
                        {
                            if (possibilities[x + i - 1, y].IsDirection((Direction)currentDirection))
                            {
                                j = 0;
                                for (int ii = (int)currentDirection; ; ii = (ii + 3) & 3)
                                {
                                    if (possibilities[x + i, y].IsDirection((Direction)ii))
                                    {
                                        if (possibilities[x + i, y + 1].IsDirection((Direction)ii))
                                        {
                                            currentDirection = (Direction)ii;
                                            x += i;
                                            path.Add(new Waypoint(new Point(x, y + 1), currentDirection));
                                            flag = true;                                            
                                            break;
                                        }
                                    }
                                    else
                                        break;
                                    j++;
                                    if (j >= 4)
                                        break;
                                }
                            }
                        }
                    }
                }
            }
        }

        static double CountHeuristics(Board board, Block block, Point blockLocation)
        {
            double result = 0.0;
            int numberOfHoles = 0;            
            board.AddBlock(block, blockLocation);
            board.RemoveLines();
            for (int y = Engine.margin; y < board.Size.Height; y++)
            {
                for (int x = Engine.margin; x < board.Size.Width - Engine.margin; x++)
                {
                    if (board.tiles[x, y])
                        result += Math.Pow(y - Engine.margin + 1, heuristicX);                    
                }
            }

            bool isSolid = false;
            for (int x = Engine.margin; x < board.Size.Width - Engine.margin; x++)
            {
                isSolid = false;
                for (int y = board.Size.Height - 1; y >= Engine.margin; y--)                
                {
                    if (board.tiles[x, y])
                        isSolid = true;
                    else
                    {
                        if (isSolid)
                            numberOfHoles++;
                    }
                }
            }
            result += heuristicA * Math.Pow(numberOfHoles, heuristicZ);
            return result;
        }

        static bool IsBlockColliding(Board board, Block block, Point blockPosition)
        {
            for (int y = 0; y < 4; y++)
            {
                for (int x = 0; x < 4; x++)
                {
                    if (block.tiles[x, y])
                    {
                        //if (y + blockPosition.Y >= mainBoard.Size.Height)
                        //    return false;
                        if ((y + blockPosition.Y >= 0) && (y + blockPosition.Y < board.Size.Height))
                            if (board.tiles[x + blockPosition.X, y + blockPosition.Y])
                                return true;
                    }
                }
            }
            return false;
        }

        public static void PaintBoard(Graphics g, int sizeX, int sizeY)
        {
            g.Clear(Color.Black);
            sizeX /= (mainBoard.Size.Width - 2);
            sizeY /= (mainBoard.Size.Height);
            g.DrawLine(boardContourPen, new Point(sizeX - 1, sizeY - 1), new Point(sizeX - 1, (1 + mainBoard.Size.Height - margin) * sizeY));
            g.DrawLine(boardContourPen, new Point((mainBoard.Size.Width + 1 - (margin << 1)) * sizeX, sizeY - 1), new Point((mainBoard.Size.Width - (margin << 1) + 1) * sizeX, (1 + mainBoard.Size.Height - margin) * sizeY));
            g.DrawLine(boardContourPen, new Point((mainBoard.Size.Width + 1 - (margin << 1)) * sizeX, sizeY - 1), new Point(sizeX - 1, sizeY - 1));
            g.DrawLine(boardContourPen, new Point((mainBoard.Size.Width + 1 - (margin << 1)) * sizeX, (1 + mainBoard.Size.Height - margin) * sizeY), new Point(sizeX - 1, (1 + mainBoard.Size.Height - margin) * sizeY));
            
            for (int y = mainBoard.Size.Height - 1; y >=  margin; y--)
            {
                for (int x = margin; x < mainBoard.Size.Width - margin; x++)
                {
                    if(mainBoard.tiles[x, y])
                        g.FillEllipse(
                            brBrick,
                            sizeX * (x - 1),
                            sizeY * (mainBoard.Size.Height - y),
                            sizeX, sizeY);
                }
            }

            if (currentBlock != null)
            {
                for (int y = 0; y < 4; y++)
                {
                    for (int x = 0; x < 4; x++)
                    {
                        if (currentBlock.tiles[x, y])
                            g.FillEllipse(
                                brMovingBrick,
                                sizeX * (x - 1 + currentBlockLocation.X),
                                sizeY * (mainBoard.Size.Height - y - currentBlockLocation.Y),
                                sizeX, sizeY);
                    }
                }
            }
        }

        internal static void PaintNextBlock(Graphics g, int sizeX, int sizeY)
        {
            g.Clear(Color.Black);
            if (Engine.nextBlock != null)
            {
                sizeX >>= 2;
                sizeY >>= 2;

                for (int x = 0; x < 4; x++)
                {
                    for (int y = 0; y < 4; y++)
                    {
                        if (Engine.nextBlock.tiles[x, 3 - y])
                            g.FillEllipse(
                                brBrick,
                                x * sizeX, y * sizeY,
                                sizeX, sizeY);
                    }
                }
            }
        }
    }
}
